package main

import (
	"fmt"
	"go-study/algorithm/standard"
)

func main() {
	lru := &LRU{
		cacheSize: 3,
		queue:     standard.NewSliceQueue(),
		hashSet:   standard.NewSet(),
	}
	lru.accessPage(1)
	lru.accessPage(2)
	lru.accessPage(5)
	lru.accessPage(1)
	lru.accessPage(6)
	lru.accessPage(7)

	lru.PrintQueue()
}

type LRU struct {
	cacheSize int
	queue     *standard.SliceQueue
	hashSet   *standard.Set
}

func (p *LRU) isQueueFull() bool {
	return p.queue.Size() == p.cacheSize
}

func (p *LRU) enQueue(pageNum int) {
	if p.isQueueFull() {
		p.hashSet.Remove(p.queue.PopBack())
	}
	p.queue.EnQueueFirst(pageNum)
}

// 当引用一个页面时，所需的页面在内存中
// 我们需要把这个页对应的节点移动到队列的前面
// 如果所需的页面不在内存中，我们将它存储在内存中
func (p *LRU) accessPage(pageNum int) {
	if !p.hashSet.Contains(pageNum) {
		p.enQueue(pageNum)
	} else if pageNum != p.queue.GetFront() {
		p.queue.Remove(pageNum)
		p.queue.EnQueueFirst(pageNum)
	}
}

func (p *LRU) PrintQueue() {
	for !p.queue.IsEmpty() {
		fmt.Print(p.queue.DeQueue(), " ")
	}
	fmt.Println()
}
